#include <string>
#include <unordered_set>

static constexpr int CHARNUMS = 26;

struct TrieNode
{
    explicit TrieNode(char key = '\0');
    ~TrieNode() = default;
    char keyChar; //这个节点代表的字符key
    bool isMatch; //是否成词的标志
    std::string pattern; //成词节点中会存储的模式串string
    TrieNode* next[CHARNUMS];
    TrieNode* fail;
    TrieNode* father;
};

class ACAutomation
{
private:
    TrieNode* root_;
    std::unordered_set<std::string> dict_; //朴素的字典，用来检查模式串是否加入
    bool ready;
    bool firstInit;

public:
    ACAutomation();
    ACAutomation(std::unordered_set<std::string>);
    ~ACAutomation();
    //通过ac自动机对文本串进行模式匹配
    void matchText(const std::string& text);
    //移除模式串
    void removePattern(const std::string& pat);
    //插入模式串，假定所有的输入字符范围在[a-z]之内
    void insertPattern(const std::string& pat);
    //查看模式串是否在ac自动机内
    bool lookupPattern(const std::string& pat);

private:
    //释放资源
    void cleanUp(TrieNode*);
    //重建fail指针
    void rebuildFailPointer();
    //清除所有fail指针，以便于重建fail链
    void clearFailPointer(TrieNode* root);
    //初始化fail指针
    void initFailPointer();
    //从ac自动机删除模式串
    void removePattern(TrieNode*, const std::string&, int);
    //检查是否就绪
    void checkReady();
};